#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e7+80000;
typedef long long LL;
inline LL read(){LL x=0,f=1;char ch=getchar();	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL primes[maxn],v[maxn],m=0;
LL sum[maxn],a[maxn];
map<LL,LL>map1;
void getprimes(LL n){
    for(LL i=2;i<=n;i++){
        if(v[i]==0){v[i]=i;primes[++m]=i;}
        for(LL j=1;j<=m;j++){
            if(primes[j]*i>n||primes[j]>v[i]) break;
            v[primes[j]*i]=primes[j];
        }
    }
}
void pre(LL n){
    for(LL i=1;i<=n;i++){
        LL temp=a[i];multiset<LL>s;
        while(temp>1&&temp%v[temp]==0){
            if(!s.count(v[temp])) map1[v[temp]]++,s.insert(v[temp]);
            temp/=v[temp];
        }
        if(temp>1){
            if(!s.count(temp)) map1[temp]++,s.insert(temp);
        }
    }
    for(LL i=1;i<=1e7;i++){
        sum[i]=sum[i-1];
        if(v[i]==i){
            sum[i]+=map1[v[i]];
        }
    }
}
int main(void)
{
  ///cin.tie(0);std::ios::sync_with_stdio(false);
  getprimes(10000100);
  LL n;scanf("%lld",&n);
  for(LL i=1;i<=n;i++) scanf("%lld",&a[i]);
  pre(n);
  LL m;scanf("%lld",&m);
  while(m--){
    LL l,r;scanf("%lld%lld",&l,&r);
    if(r>=1e7) r=1e7;
    if(l>=1e7) l=1e7;
    printf("%lld\n",sum[r]-sum[l-1]);
  }
return 0;
}
